The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


8.2.2 Byte Sequences with Given Difference

In generating A and with a specific difference δ, one must generate four pairs of byte sequences (σj, σ´j), each with a specific difference δj, where σj = {σji} and σ´j = {σ´ji}. The inputs to the four S-boxes used to produce these values are {0, 2, 4, ..., 38} (whereas they axe 1, 3, 5, ..., 39} for B). Therefore our byte sequences are given by σji = sj [2i] and σ´ji = j[2i]. Hence any questions about difference byte sequences reduce to questions about the sequences

{sj[0], sj[2],...,sj[38]}, {s´j[0], s´j[2],...,s´j[38]}

For a given δj we will estimate the chance that there exists a pair (σj, σ´j) with that difference sequence.

We can model each byte sequence generated by a key-dependent S-box as a randomly selected non-repeating byte sequence of length 20. This allows us to make many useful predictions about the likelihood of finding keys or pairs of keys with various interesting properties. Because we will be analyzing the key schedule using this assumption in the remainder of this section, we should discuss how reasonable it is to treat this byte sequence as randomly generated. As discussed in Section 7.2.3, we have not found any statistical deviations between our key-dependent S-boxes and the random model in any of our extensive statistical tests.

Not all byte sequences are possible; due to the bijectivity of the S-boxes we know that all the bytes in the sequence are distinct. There are 256!/236! of those sequences, which is close to 2159.

Each key-dependent S-box uses N/8 bits of key material; hence, if the S-boxes were truly random we would expect two 20-byte sequences to create the desired difference with probability roughly 2N/4-1. 2-160 (There are 2N/4-1 pairs of byte sequences, and each has a 2-160 chance of being a match.) For example, for N = 256 we expect with probability 2-97 that there exists a pair of our S-boxes that produces the desired difference sequence. Note that this probability is for any specific difference sequence. There are many such possible difference sequences, and of course some of those actually occur. Attacks requiring a specific difference sequence seem more likely than attacks requiring any of a class of 297 usable difference sequences.

Most difference sequences in A will require that all four δj are non-zero. For a randomly chosen difference δ in the A sequence we thus expect that there are two keys that generate exactly this difference with probability about 2-388.

8.2.3 Identical Byte Sequences

As discussed in section 8.1.2, we have empirically verified that there are no equivalent S-box keys that generate the same sequence of 20 bytes. That holds for our specific choice of q0 and q1. This section analyzes the probability of two identical sequences occurring for arbitrary q-boxes.

The estimate of section 8.2.2 holds for the special case of δj being the all-zero sequence. If we are a little more careful, then we can actually improve the estimate for this case. While this result shows that the S-boxes are not uniformly distributed throughout the space of all possible 8-bit S-boxes, it shows that the S-boxes display better than average differences in this particular case.

To improve the estimate, we peel off one layer of our q construction and assume the rest of the construction is random. Without loss of generality we look at2


2:For ease of discussion, we number the key bytes as k0,..., k3 going into one S-box. The actual byte ordering for s0 and a 256-bit key’s subkey-generating S-box is k0, k8, k16, k24. The numbering of the key bytes has no effect on the security arguments in this section.

s1(x) = q0[q0[q1[q1[q0[x] ⊕ k0] ⊕ k1] ⊕ k2] ⊕ k3]

Identical sequences are possible only if the inputs to the last q0 fixed permutation are identical for both sequences. That means that the task of finding a pair of identical sequences comes down to a simpler task: finding a pair of (k0, k1, k2) byte values that leads to a pair of sequences before the XOR with k3 that have a fixed XOR difference. Then, k3 can be changed to include the XOR difference, and identical sequences of inputs will go into the last q0 S-box.

Let

t[i]:= q0[q1[q1[q0[i] ⊕ k0] ⊕ k1] ⊕ k2]

The goal is to find a pair of t[i] sequences such that

t[i] ⊕ t*[i] = constant

Let us assume that t generates a random sequence (with the restriction that all byte values must be distinct). The chances of any pair of t, t* generating such a constant difference is about 2-151. (The domain in which we are searching for collisions is the set of all 19-byte sequences with non-repeated values. There are 256!/237! of these sequences, which is close to 2151.) This brings the chance of finding a pair with such a constant difference down to 247. 2-151 = 2-104.

8.2.4 The A and B Sequences

From the properties of the byte sequences, we can discuss the properties of the A and B sequences generated by each key M.

Ai = MDS(s0(2i, Me), s1(2i, Me), s2(2i, Me), s3(2i, Me))

Since the MDS matrix multiply is invertible, and since i is different for each round’s subkey words generated, we can see that no A or B value can repeat itself.

Similarly, we can see from the construction of h that each key byte affects exactly one S-box used to generate A or B. Changing a single key byte always alters every one of the 20 bytes of output from that S-box; the MDS matrix ensures that every byte of every word in the 20-word A or B sequence to which this key byte contributes is altered.

Consider a single byte of output from one of the S-boxes. If we cycle any one of the key bytes that contributes to that S-box through all 256 possible values, the output of the S-box will also cycle through all 256 possible values. If we take four key bytes that contribute to four different S-boxes, and we cycle those four bytes through all possible values, then the result of h will also cycle through all possible values. This proves that A and B are uniformly distributed for all key lengths, assuming the key M is uniformly distributed.

8.2.5 The Sequence (K2i, K2i+1)

As Ai and Bi are uniformly distributed (over all keys), so are all the Ki. As all pairs (Ai, Bi are distinct, all the pairs (K2i, K2i+1) are distinct, although it might happen that Ki = Kj for any pair of i and j.


Previous Table of Contents Next